`
https://leetcode.cn/problems/swim-in-rising-water/
`

/**
 * @param {number[][]} grid
 * @return {number}
 */
var swimInWater = function (grid) {
  const n = grid.length
  const dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]

  const isValid = (x, y) => x >= 0 && y >= 0 && x < n && y < n

  // 在只访问 grid[x][y] <= mx 的情况下，能否到达终点
  const check = (mx) => {
    const vis = new Set()

    const dfs = (i, j) => {
      // 到达终点
      if (i === n - 1 && j === n - 1) return true
      // 避免重复访问
      vis.add(`${i}-${j}`)
      for (const [x, y] of dirs.map(([x, y]) => [x + i, y + j])) {
        if (isValid(x, y) && grid[x][y] <= mx && !vis.has(`${x}-${y}`) && dfs(x, y)) {
          return true
        }
      }
      return false
    }

    return dfs(0, 0)
  }

  // 起点和终点一定在路径上，- 1 后 grid[x][y] <= mx 的路径不存在
  let left = Math.max(grid[0][0], grid[n - 1][n - 1]) - 1
  // 终点已经开放一定能到达终点
  let right = n * n - 1
  while (left + 1 < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (check(mid)) {
      right = mid
    } else {
      left = mid
    }
  }
  return right
};